package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No216组合总和III {

    /**
     * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
     *
     * 说明：
     * 所有数字都是正整数。
     * 解集不能包含重复的组合。 
     * 示例 1:
     * 输入: k = 3, n = 7
     * 输出: [[1,2,4]]
     * 示例 2:
     * 输入: k = 3, n = 9
     * 输出: [[1,2,6], [1,3,5], [2,3,4]]
     */

    private List<List<Integer>> lists=new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
//        dg(k,0,n,0,new ArrayDeque<>());
        dgGood(k,0,n,0,1,new ArrayList<>());
        return lists;
    }

    private Set<List<Integer>> listSet=new HashSet<>();
    private boolean[] flag=new boolean[10];
    /**
     * 这样写复杂度,很高,还利用了flag标志位和set,我们可以直接用start,控制下一层for遍历的起点,即可达到唯一性
     * @param k k个数
     * @param count 当前用了几个数
     * @param n 目标之和
     * @param sum 当前之和
     * @param list 存入的数
     */
    private void dg(int k, int count, int n, int sum, Deque<Integer> list){

        if(sum==n&&count==k){
            System.out.println("正好相等,加入结果集");
            ArrayList<Integer> integers = new ArrayList<>(list);
            integers.sort(Comparator.comparingInt(a -> a));
            if(listSet.contains(integers)){
                return;
            }
            lists.add(integers);
            listSet.add(integers);
            return;
        }

        for (int i = 1; i < 10; i++) {
            if(flag[i]||count>k||sum>n)
                continue;

            flag[i]=true;
            sum+=i;
            list.addLast(i);

            dg(k,count+1,n,sum,list);

            flag[i]=false;
            sum-=i;
            list.removeLast();
        }

    }

    private void dgGood(int k,int count,int n,int sum,int start,List<Integer> list){

        if(n==sum&&k==count){
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < 10; i++) {
            if(sum>n||count>=k)
                continue;
            sum+=i;
            list.add(i);
            /**
             * 一定要注意,这里是i+1,并非是start+1
             */
            dgGood(k,count+1,n,sum,i+1,list);
            sum-=i;
            list.remove(list.size()-1);
        }

    }

    public static void main(String[] args) {
        No216组合总和III n=new No216组合总和III();
        List<List<Integer>> lists = n.combinationSum3(2, 4);
        System.out.println(JSON.toJSONString(lists));
    }

}
